Thuật toán dijkstra là gì? Các bài báo nghiên cứu khoa học

Khái niệm và bối cảnh ra đời

Thuật toán Dijkstra là một thuật toán kinh điển dùng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh còn lại trong một đồ thị có trọng số không âm. Thuật toán này được đề xuất bởi nhà khoa học máy tính người Hà Lan Edsger W. Dijkstra vào năm 1956 và được công bố chính thức năm 1959. Trong lịch sử phát triển của khoa học máy tính, đây là một trong những thuật toán sớm nhất thể hiện rõ tư duy thuật toán hiện đại, đặc biệt là chiến lược tham lam (greedy strategy).

Bối cảnh ra đời của thuật toán gắn liền với nhu cầu tối ưu hóa việc định tuyến trong các hệ thống mạng và hạ tầng giao thông. Ở thời điểm đó, máy tính còn rất hạn chế về tài nguyên, vì vậy một thuật toán vừa đúng vừa hiệu quả về mặt tính toán là yêu cầu then chốt. Dijkstra đã thiết kế thuật toán sao cho mỗi bước đều đưa ra quyết định cục bộ tối ưu, đồng thời vẫn đảm bảo tính tối ưu toàn cục.

Cho đến nay, thuật toán Dijkstra vẫn giữ vai trò nền tảng trong giảng dạy và nghiên cứu thuật toán. Nhiều biến thể và cải tiến của nó được phát triển để phục vụ các bài toán thực tế có quy mô lớn như hệ thống bản đồ số, mạng viễn thông và các hệ thống phân tán.

• Là thuật toán tìm đường đi ngắn nhất một nguồn
• Dựa trên chiến lược tham lam
• Yêu cầu trọng số cạnh không âm
• Có nhiều biến thể và cải tiến hiện đại

Bài toán đường đi ngắn nhất

Bài toán đường đi ngắn nhất (shortest path problem) là một lớp bài toán cơ bản trong lý thuyết đồ thị. Mục tiêu là tìm một đường đi giữa hai đỉnh hoặc từ một đỉnh nguồn đến tất cả các đỉnh khác sao cho tổng trọng số các cạnh trên đường đi là nhỏ nhất. Trọng số có thể biểu diễn nhiều đại lượng khác nhau như khoảng cách, chi phí, thời gian hoặc mức tiêu hao tài nguyên.

Thuật toán Dijkstra giải quyết biến thể phổ biến nhất của bài toán này: tìm đường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh còn lại trong đồ thị. Kết quả của thuật toán thường được biểu diễn dưới dạng một mảng khoảng cách và một cây đường đi ngắn nhất (shortest path tree).

Bài toán này có nhiều biến thể khác nhau tùy theo ràng buộc:

• Đường đi ngắn nhất giữa một cặp đỉnh
• Đường đi ngắn nhất từ một nguồn đến tất cả các đỉnh
• Đường đi ngắn nhất giữa mọi cặp đỉnh

Trong số các biến thể trên, Dijkstra phù hợp nhất với bài toán từ một nguồn duy nhất, với điều kiện đồ thị không chứa cạnh có trọng số âm.

Biến thể bài toán	Thuật toán thường dùng
Một nguồn – mọi đỉnh	Dijkstra
Cạnh có trọng số âm	Bellman–Ford
Mọi cặp đỉnh	Floyd–Warshall

Mô hình đồ thị và các giả định

Thuật toán Dijkstra hoạt động trên mô hình đồ thị toán học được ký hiệu là G = (V, E), trong đó V là tập các đỉnh và E là tập các cạnh. Mỗi cạnh (u, v) trong đồ thị được gán một trọng số w(u, v), biểu diễn chi phí để đi từ đỉnh u đến đỉnh v.

Đồ thị có thể là đồ thị có hướng hoặc vô hướng. Trong đồ thị có hướng, cạnh (u, v) chỉ cho phép di chuyển từ u đến v. Trong đồ thị vô hướng, cạnh cho phép di chuyển theo cả hai chiều. Thuật toán Dijkstra có thể áp dụng cho cả hai loại đồ thị này mà không cần thay đổi bản chất.

Giả định quan trọng và bắt buộc nhất của thuật toán là mọi trọng số cạnh đều không âm. Điều này đảm bảo rằng khi một đỉnh đã được chọn là có khoảng cách ngắn nhất tạm thời, thì khoảng cách đó sẽ không còn bị cải thiện trong các bước sau.

• Trọng số cạnh ≥ 0
• Đồ thị hữu hạn
• Có thể tồn tại hoặc không tồn tại đường đi giữa các đỉnh

Nếu giả định về trọng số không âm bị vi phạm, thuật toán có thể cho kết quả sai do chiến lược tham lam không còn đảm bảo tính đúng đắn.

Ý tưởng cốt lõi của thuật toán

Ý tưởng trung tâm của thuật toán Dijkstra là xây dựng dần dần tập các đỉnh mà khoảng cách ngắn nhất từ nguồn đã được xác định chắc chắn. Ở mỗi bước, thuật toán chọn đỉnh chưa được xét có khoảng cách tạm thời nhỏ nhất và coi khoảng cách đó là tối ưu.

Sau khi chọn được đỉnh u, thuật toán tiến hành nới lỏng (relaxation) tất cả các cạnh đi ra từ u. Nới lỏng cạnh là quá trình kiểm tra xem việc đi qua u có giúp cải thiện khoảng cách đến đỉnh kề v hay không.

Công thức nới lỏng cạnh được mô tả như sau:

$\text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + w(u, v))$

Quá trình này được lặp lại cho đến khi tất cả các đỉnh đều đã được xét hoặc không còn đỉnh nào có thể tiếp cận từ nguồn. Kết quả cuối cùng là tập các khoảng cách ngắn nhất từ nguồn đến từng đỉnh.

1. Khởi tạo khoảng cách
2. Chọn đỉnh có khoảng cách nhỏ nhất
3. Nới lỏng các cạnh kề
4. Cố định đỉnh đã chọn

Chiến lược tham lam đảm bảo rằng mỗi bước lựa chọn đều đơn giản, nhưng vẫn dẫn đến nghiệm tối ưu trong phạm vi các giả định đã đặt ra.

Các bước thực hiện cơ bản

Thuật toán Dijkstra được mô tả thông qua một chuỗi các bước xác định, nhằm đảm bảo mỗi đỉnh được xử lý đúng một lần theo thứ tự tăng dần của khoảng cách ngắn nhất từ đỉnh nguồn. Quá trình này giúp thuật toán duy trì tính đúng đắn và tránh việc phải quay lui hay cập nhật lại các đỉnh đã được cố định.

Bước đầu tiên là khởi tạo. Tất cả các đỉnh trong đồ thị được gán khoảng cách ban đầu là vô cùng, ngoại trừ đỉnh nguồn có khoảng cách bằng 0. Đồng thời, một tập hoặc mảng đánh dấu được sử dụng để theo dõi trạng thái đã xét hay chưa xét của mỗi đỉnh.

Ở mỗi vòng lặp, thuật toán chọn ra đỉnh chưa xét có khoảng cách tạm thời nhỏ nhất. Đỉnh này được coi là đã tìm được khoảng cách ngắn nhất cuối cùng và sẽ không bị cập nhật lại trong các bước tiếp theo.

• Khởi tạo dist[source] = 0, dist[v] = ∞ với mọi v ≠ source
• Chọn đỉnh u chưa xét có dist[u] nhỏ nhất
• Nới lỏng tất cả các cạnh (u, v)
• Đánh dấu u là đã xét

Quy trình kết thúc khi tất cả các đỉnh đều đã được xét hoặc khi các đỉnh còn lại không thể tiếp cận từ nguồn. Kết quả thu được là khoảng cách ngắn nhất từ nguồn đến từng đỉnh trong đồ thị.

Cấu trúc dữ liệu thường sử dụng

Hiệu năng của thuật toán Dijkstra phụ thuộc lớn vào cách cài đặt và cấu trúc dữ liệu được lựa chọn. Cách cài đặt đơn giản nhất sử dụng mảng để lưu trữ khoảng cách và duyệt tuyến tính để tìm đỉnh có khoảng cách nhỏ nhất ở mỗi bước.

Trong các hệ thống thực tế hoặc bài toán có quy mô lớn, hàng đợi ưu tiên (priority queue) hoặc heap nhị phân thường được sử dụng để tối ưu hóa bước lựa chọn đỉnh. Khi đó, thao tác lấy đỉnh có khoảng cách nhỏ nhất trở nên nhanh hơn đáng kể.

Cấu trúc dữ liệu	Thời gian chọn đỉnh nhỏ nhất
Mảng	O(V)
Heap nhị phân	O(log V)
Fibonacci heap	O(1) trung bình

Trong thực hành, heap nhị phân thường được ưu tiên do dễ cài đặt và có hiệu năng ổn định, trong khi Fibonacci heap chủ yếu được sử dụng trong phân tích lý thuyết.

Độ phức tạp thời gian và không gian

Độ phức tạp thời gian của thuật toán Dijkstra thay đổi tùy theo cấu trúc dữ liệu. Với cách cài đặt đơn giản sử dụng mảng, thuật toán có độ phức tạp O(V²), phù hợp với đồ thị nhỏ hoặc đồ thị dày.

Khi sử dụng heap nhị phân, độ phức tạp được cải thiện thành O((V + E) log V), trong đó V là số đỉnh và E là số cạnh. Đây là mức độ phức tạp phổ biến nhất trong các ứng dụng thực tế.

Về mặt không gian, thuật toán yêu cầu bộ nhớ O(V) để lưu trữ mảng khoảng cách, mảng đánh dấu và thông tin truy vết đường đi. Chi phí bộ nhớ này được coi là hợp lý đối với hầu hết các hệ thống hiện đại.

So sánh với các thuật toán liên quan

Dijkstra không phải là thuật toán duy nhất giải quyết bài toán đường đi ngắn nhất. Tùy vào đặc điểm của đồ thị và yêu cầu bài toán, các thuật toán khác có thể phù hợp hơn.

Thuật toán Bellman–Ford cho phép xử lý đồ thị có cạnh trọng số âm, nhưng phải đánh đổi bằng độ phức tạp cao hơn. Thuật toán Floyd–Warshall giải quyết bài toán đường đi ngắn nhất giữa mọi cặp đỉnh, nhưng chỉ phù hợp với đồ thị nhỏ do chi phí O(V³).

• Dijkstra: nhanh, yêu cầu trọng số không âm
• Bellman–Ford: chậm hơn, hỗ trợ trọng số âm
• Floyd–Warshall: đơn giản, chi phí cao

Việc lựa chọn thuật toán phụ thuộc trực tiếp vào ràng buộc dữ liệu và mục tiêu của hệ thống.

Ứng dụng thực tế

Thuật toán Dijkstra được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Một trong những ứng dụng phổ biến nhất là định tuyến mạng, nơi thuật toán được dùng để xác định đường đi tối ưu cho các gói tin trong mạng máy tính.

Trong lĩnh vực bản đồ số và hệ thống dẫn đường, Dijkstra hoặc các biến thể của nó được sử dụng để tính toán lộ trình ngắn nhất hoặc nhanh nhất giữa hai địa điểm, dựa trên dữ liệu giao thông và khoảng cách.

Ngoài ra, thuật toán còn xuất hiện trong các bài toán lập lịch, phân tích mạng xã hội, tối ưu hóa logistics và nhiều hệ thống ra quyết định khác, nơi việc tối ưu chi phí là yếu tố cốt lõi.

Hạn chế và các hướng mở rộng

Hạn chế lớn nhất của thuật toán Dijkstra là không thể xử lý đồ thị có cạnh trọng số âm. Điều này khiến thuật toán không phù hợp với một số bài toán kinh tế hoặc tài chính, nơi chi phí có thể mang giá trị âm.

Đối với đồ thị rất lớn, chi phí tính toán và bộ nhớ cũng trở thành vấn đề. Vì lý do đó, nhiều biến thể và thuật toán mở rộng đã được đề xuất, chẳng hạn như A* (sử dụng heuristic) hoặc các thuật toán định tuyến phân cấp.

Những hướng mở rộng này vẫn giữ lại ý tưởng cốt lõi của Dijkstra nhưng được điều chỉnh để phù hợp hơn với yêu cầu thực tế.

Tài liệu tham khảo

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Princeton University, Algorithms, Part II – Shortest Paths. https://algs4.cs.princeton.edu/44sp/
• Stanford University, CS161: Design and Analysis of Algorithms – Shortest Paths. https://web.stanford.edu/class/cs161/
• E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, 1959.